Feature #7: Maximum Users
Implement the "Maximum Number of Users" feature for our "Cellular Operator AT&T" project.
We'll cover the following
Description#
On a busy intersection with heavy vehicular and pedestrian traffic, the operator deploys a base station. The number of users connected to that base station keeps changing rapidly, as people enter and leave its coverage area. The base station quickly dumps the current number of users to a list every 1 ms.
The operator wants to analyze the data to improve coverage for its users. However, the data contains rapid variations that don’t carry useful information from a network management perspective. To deal with the variation, the operator wants to find the maximum number of users connected to the base station in every k ms sliding window.
Given a list of values, we need to create a sliding window of size k (shown in red) and find the max in each sliding window. Different sliding windows in the given list are shown in separate rows in the following illustration, along with the maximum value in the sliding window.
Solution#
Here, we will find the maximum number of users who are connected to the base station in the selected k millisecond windows. Each entry in the array will show the number of users who are connected to the base station in the 1 ms window.
Here is how we will implement this feature:
-
We are given an array of integers.
-
If the value at the current index is less than the value at the previous index of the array or all the value(s) of the index(es) in
mqueue, then we will push the current index to themqueue. Otherwise, we will perform the pop operation. -
During the
Enum.reduceexecution, if themqueuevalue (index) at zero index is equal to thei-k, then we will perform theremove_leftoperation in themqueue. -
If the index of the given array is greater than or equal to the window slide length (
k), then we will push the maximum value of themqueueto theresultarray.
This way, the result array will contain the maximum number for each window slide (k).
The following illustrations show us how the solution given above will work:
1 of 28
2 of 28
3 of 28
4 of 28
5 of 28
6 of 28
7 of 28
8 of 28
9 of 28
10 of 28
11 of 28
12 of 28
13 of 28
14 of 28
15 of 28
16 of 28
17 of 28
18 of 28
19 of 28
20 of 28
21 of 28
22 of 28
23 of 28
24 of 28
25 of 28
26 of 28
27 of 28
28 of 28
Let’s look at the solution code below:
Complexity measures#
| Time complexity | Space complexity |
|---|---|
Time complexity#
Here, we are iterating the outer Enum.reduce function n times and calling the inner recursion function, update_mqueue, k times. Here, n is the size of the given array, and k is the size of the sliding window, which is constant. Therefore, the time complexity will be .
Space complexity#
The space complexity will be , because we need to store a maximum of k values in the mqueue.
Feature #6: Densest Deployment
Feature #8: Maximum Signal Strength